#include <stdio.h>
#include <stdlib.h>
typedef int DataType;

struct  node
{
    DataType  element;//表示当前数据
    struct node  *next;//指向下一个结点的指针
};
typedef struct node * SET;



void insert(DataType datax, SET set);

/*
  函数名： InitSet
  函数功能：根据参数num，初始化集合
  函数参数：集合元素的个数
  返回值：集合头指针
*/
SET InitSet(int num)
{

    SET p;
    p = ( struct  node *)malloc(sizeof(struct node)) ;
    p->next = NULL;
    p->element = num;
    int temp;
    for(int i =0;i<num;i++)
    {
        scanf("%d",&temp);
        insert(temp, p); //调用insert函数，将输入数据插入集合
    }
    return p;
}


/*
  函数名： find
  函数功能：在集合中查找值为datax的成员
  函数参数：datax:待查找的值 ； set：集合的头结点
  返回值：找到值为datax的成员返回1，否则返回0
*/
int find(DataType datax, SET  set)
{
    //请在此处填写代码，在set集合中查找值为datax的成员，若找到返回1，否则返回0
    /**********  Begin  **********/
    if(set==NULL||set->element==0)
        return 0;
    SET p;
    p=set->next;
    while(p!=NULL&&p->element!=datax)
    {
        p=p->next;
    }
    if(p==NULL)
        return 0;
    else
        return 1;

    /**********   End   **********/
}

/*
  函数名： insert
  函数功能：在集合set中插入值为datax的成员 ，插入位置在表头
  函数参数：datax:待插入的值 ； set：集合的头结点
  返回值：无
  时间复杂度：O（1）
*/
void insert(DataType datax, SET set)
{
    //请在此处填写代码，将datax插入集合set， 注意因集合元素是无序的，只需将新成员插入表头
    /**********  Begin  **********/
    SET p=( struct  node *)malloc(sizeof(struct node));
    p->element=datax;
    p->next=NULL;
    if(set==NULL)
    {
        set=p;
    }
    else
    {
        p->next=set->next;
        set->next=p;
    }
    set->element++;

    /**********   End   **********/
}

/*
  函数名： copyList
  函数功能：将集合setA复制生成集合setB
  函数参数：setA 、setB的头结点
  返回值：无
*/
void copySet(SET setA, SET setB)
{
    //请在此处填写代码，实现将集合setA的成员复制到集合setB的功能
    /**********  Begin  **********/
    if(setA==NULL||setA->element==0)
        return ;
    SET p;
    p=setA->next;
    while(p!=NULL)
    {
        insert(p->element,setB);
        p=p->next;
    }

    /**********   End   **********/
}

/*
  函数名： printSet
  函数功能：输出集合的元素，以空格作为元素之间分界符
  函数参数：set的头结点
  返回值：无
*/
void printSet(SET set)
{
    //请在此处填写代码，实现输出集合元素的功能，元素之间以空格为分界符
    /**********  Begin  **********/
    SET q;
    q=set->next;
    int i;
    while(q!=NULL)
    {
        i=q->element;
        printf("%d ",i);
        q=q->next;
    }

    /**********  End  **********/
}

/*
  函数名： setUnion
  函数功能：求两个集合setA 和 setB的并集
  函数参数：setA和setB的头结点
  返回值：并集集合的头结点
*/
SET setUnion(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
    SET setC=( struct  node *)malloc(sizeof(struct node));
    SET p;

    setC->element=0;
    setC->next=NULL;
    if(setA==NULL||setA->element==0)
        setC=setA;
    else if(setB==NULL||setB->element==0)
        setC=setB;
    else
    {
        copySet(setA,setC);
        p=setB->next;
        while(p!=NULL)
        {
            if(find(p->element,setC)==0)
                insert(p->element,setC);
            p=p->next;
        }
    }
    return setC;
    /**********  End  **********/
}

/*
  函数名： setIntersect
  函数功能：求两个集合setA 和 setB的交集
  函数参数：setA和setB的头结点
  返回值：交集集合的头结点
*/
SET setIntersect(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
    if(setA==NULL||setA->element==0||setB==NULL||setB==0)
        return NULL;
    SET q=( struct  node *)malloc(sizeof(struct node));
    q->element=0;
    q->next=NULL;
    SET p=setA->next;
    while(p!=NULL)
    {
        if(find(p->element,setB)==1)
            insert(p->element, q);
        p=p->next;
    }
    return q;
    /**********  End  **********/
}

/*
  函数名： setExcept
  函数功能：求两个集合setA 和 setB的差
  函数参数：setA和setB的头结点
  返回值：结果集合的头结点
*/
SET setExcept(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
    if(setA==NULL||setA->element==0)
        return NULL;
    if(setB==NULL||setB->element==0)
        return setA;
    SET setC=( struct  node *)malloc(sizeof(struct node));
    setC->element=0;
    setC->next=NULL;
    SET p=setA->next;
    while(p!=NULL)
    {
        if(find(p->element,setB)==0)
            insert(p->element,setC);
        p=p->next;
    }
    return setC;
    /**********  End  **********/
}

void destroySet(SET set)
{
//释放存储集合的链表空间，表头为set
    SET p=set->next;
    while(p!=NULL)
    {
        free(set);
        set=p;
        p=p->next;
    }
    free(p);
}